package cn.mengfly.algorithm.collection.stack;

import java.util.Iterator;

/**
 * 基于链表实现的栈，无需扩容
 *
 * @author wangp
 */
public class LinkedStack<T> implements Stack<T> {

    private Node<T> head;
    int size = 0;


    @Override
    public void push(T t) {
        Node<T> node = new Node<>();
        node.item = t;

        Node<T> oldHead = head;

        head = node;
        head.next = oldHead;

        size++;
    }

    @Override
    public T pop() {
        if (size == 0) {
            return null;
        }
        Node<T> pop = head;
        head = head.next;

        size--;
        pop.next = null;

        return pop.item;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            LinkedStack.Node<T> curNode = head;

            @Override
            public boolean hasNext() {
                return curNode == null;
            }

            @Override
            public T next() {
                final T item = curNode.item;
                curNode = curNode.next;
                return item;
            }
        };
    }

    @Override
    public T peak() {
        if (head == null) {
            return null;
        }
        return head.item;
    }

    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.item = null;
            x.next = null;
            x = next;
        }
        this.head = null;
        this.size = 0;
    }

    private static class Node<T> {
        T item;
        Node<T> next;
    }
}
